package com.jsn.buildbase.algorithm

import com.jsn.baselibx.utils.Logs
import java.lang.IllegalArgumentException
import java.lang.RuntimeException
import java.util.*
import java.util.concurrent.Semaphore
import kotlin.collections.ArrayList
import kotlin.math.pow












/*fun findPaths(m: Int, n: Int, N: Int, i: Int, j: Int): Int {
    //boarder: m-1,n-1

}*/

// start from first preorder element
/*
*/
/*2,3*/

/*输入: "the sky is blue"
输出: "blue is sky the"*/

/*输入：
"  hello world!  "
输出：
"  world! hello  "
预期：
"world! hello"*/

/*
输入：
"a good   example"  a,good,example example
输出：
"example   good a"  a,good,_,example
预期：
"example good a"*/


/*linkhashmap<K,V>*/
/* head->node1->node2->node3->node4<-tail
*
*
* */

/*输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]*/
fun restoreIpAddresses(s: String): List<String> {
    if(s.length<4) throw RuntimeException()
    val length = s.length
    val slug=length-1
    val dotCount=3

    //todoe
    return emptyList()
}

fun c(m:Int,n:Int):Int{
    //assume m is larger than n
    if(m <n) throw IllegalArgumentException()
    if(m==n )  return 1
    if(n==1) return m
        return m * c(m-1,n-1)
}

fun reverseWords(s: String): String {
    val trim = s.trim()

    val splitedStrings: List<String> = trim.split(" ", limit = Int.MAX_VALUE)

    return splitedStrings.map { it.trim() }.filter { !it.equals(" ") }
            .reversed()
            .reduce({ accumulation, pendingString->
                Logs.e("acc:$accumulation,append:$pendingString")
                accumulation+" "+pendingString

           })
}

fun multiply(num1: String, num2: String): String {
    var base=1
    var res: Int =0
    //List<Char>
    num2.toList().reversed().forEach {
        res+= ((base * num1.toInt() * it.toString().toInt()))
        Logs.e("nums1:$num1 it:${it.toInt()}")
        base*=10
    }
    return res.toString()
}

fun getInt(num:String): Int {
    val length = num.length
    var res:Int=0
    val base: Int = 10
    for(i in 0..length-1){
        val times = length - 1 - i
        res+=(num.get(i).toInt() * base.toFloat().pow(times)).toInt()
    }
    return res
}

fun checkInclusion(s1: String, s2: String): Boolean {
    return false
}



val set= mutableSetOf<String>()
fun lengthOfLongestSubstring(s: String): Int {
    if(s.isEmpty()) return 0
    var res=1
    for(i in 0..s.length-1){
        set.clear()
        var len=0
        for(j in i..s.length-1){
            if(set.add(s.get(j).toString()))
                len++
            else{
                break
            }
        }
        res=if(len>=res) len else res
    }
    return res
}

fun longestCommonPrefix(strs: Array<String>): String {
    if(strs.isEmpty()) return ""
    var index=0
    var set= mutableSetOf<String>()
    val min = strs.map { it.length }.min()
    while (true){
        set.clear()
        if(index>min!!-1) break
        val toSet = strs.map {
            it.get(index)
        }.toSet()
        if(toSet.size==1){
            index++
        }else break
    }
    if(index==0) return ""
    return strs[0].substring(0,index)


}



//[1,2] [2,1]
val map= mutableMapOf<Int,Int>()
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
    if(preorder.size==0) return null

    map.apply {
        var index=0
        for (i in preorder) {
            map.put(i,index++)
        }
    }

    return null

}

/*锯齿层次遍历*/
fun zigzagLevelOrder(root: TreeNode?): List<List<Int>> {

    if(root==null) return emptyList()

    val result = mutableListOf<List<Int>>()
    var right =true
    var currentLayerOfTree = mutableListOf<TreeNode>().apply { add(root) }

    while (currentLayerOfTree.size>0){
        val temp=mutableListOf<TreeNode>().apply { addAll(0,currentLayerOfTree) }
       // currentLayerOfTree.clear()

        result.add(temp.map { node-> node.`val` })

        temp.reverse()

        currentLayerOfTree=temp.flatMap {node->
            mutableListOf<TreeNode>().apply {
                if(right)  {
                    node.right?.also { add(it) }
                    node.left?.also { add(it) }
                }
                else{
                    node.left?.also { add(it) }
                    node.right?.also { add(it) }
                }
            }
        } .toMutableList()
        right=!right
    }
    return result
}



//层次遍历
fun levelOrder(root: TreeNode?): List<List<Int>> {
    val list = mutableListOf<List<Int>>()
    val queue :Queue<TreeNode?> = LinkedList<TreeNode?>()
    root?.apply {
        queue.add(root)
    }
    while(!queue.isEmpty()){
        val layer = mutableListOf<Int>()
        queue.forEach {
            layer.add(it!!.`val`)
        }
        list.add(layer.toList())
        val clone = queue.run {
            val queue1 :Queue<TreeNode?> = LinkedList<TreeNode?>()
            forEach {
                queue1.add(it)
            }
            queue1
        }
        queue.clear()
        clone.forEach {
            it!!.left?.apply { queue.add(it.left) }
            it!!.right?.apply { queue.add(it.left) }
        }
    }
    return list
}

fun isSymmetric(root: TreeNode?): Boolean {
    root?.apply {
        return  isMirror(root.left,root.right)
    }
    return true
}

fun isMirror(left:TreeNode?,right:TreeNode?):Boolean{
    if(left==null &&right==null) return true
    if(left==null ||right==null) return false
    return (left.`val`==right.`val`)
            &&(isMirror(left.right,right.left)
            &&(isMirror(left.left,right.right)))
}





fun twoSum(nums: IntArray, target: Int): IntArray {
    val res=IntArray(2)
    for(i in 0 until nums.size-1){
        val i1 = target - nums[i]
        for(a in i+1 until nums.size){
            if(nums[a]==i1){
                res[0]=i
                res[1]=a
            }
            return res
        }
    }
    return res
}

fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
    var a=l1
    var b=l2
    var temp=0
    if(a==null&&b==null) return null
    var end:ListNode
    var res=ListNode(0).apply {
        val node=this
        a?.run { node.`val`+=this.`val` }
        b?.run { node.`val`+=this.`val` }
        if(`val`>=10) {
            `val`-=10
            temp=1
        }
        a= a?.next
        b= b?.next
    } .also { end=it }

    while (a!=null||b!=null){
        end.next=ListNode(0).apply {
            val node=this
            a?.run { node.`val`+=this.`val` }
            b?.run { node.`val`+=this.`val` }
            `val`+=temp
            if(`val`>=10) {
                `val`-=10
                temp=1
            }else{
                temp=0
            }
            a=a?.next
            b=b?.next
        } .also { end=it }
    }

    if(temp==1){
        end.next=ListNode(1)
    }

    return  res
}

fun caculate(l:ListNode?) :Int{
        var res=0
         l?.apply {
             res+=`val`+ caculate(l.next)
         }
    return res
}


class ListNode(var `val`: Int) {
        var next: ListNode? = null
    }

class TreeNode(var `val`: Int) {
         var left: TreeNode? = null
         var right: TreeNode? = null
     }

var index=0

fun recoverTree(root: TreeNode?): Unit {
    val list=ArrayList<Int>()
    inorder(root,list)
    list.sort()
    _recoverTree(root,list)
}

fun _recoverTree(root: TreeNode?, list: ArrayList<Int>) {

        root?.apply {

            root.left?.apply {
                _recoverTree(root.left,list)
            }

            root.`val`=list.get(index)

            index++

            root.right?.apply {
                _recoverTree(root.right,list)
            }
        }
}

fun inorder(root:TreeNode?,array:ArrayList<Int>){
    root?.apply {

        root.left?.apply {
            inorder(root.left,array)
        }
        array.add(`val`)

        root.right?.apply {
           inorder(root.right,array)
        }
    }
}

fun morris(){

}

